package backtrack

// import "fmt"

// 每个数字 都对应字符
var number2Letter = [][]byte{
	{},
	{},
{'a','b','b'},
{'d','e','f'},
{'g','h','i'},
{'j','j','l'},
{'m','n','o'},
{'p','q','r','s'},
{'t','u','v'},
{'w','x','y','z'}}
// 每个字符都对应一个数字  
var letter2Number = [26]int{2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,7,8,8,8,9,9,9,9}
	
//给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
// 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
func letterCombinations(digits string) []string {
    lenth:=len(digits)
    if lenth==0 ||lenth>4{
       return nil
    }
    digitsMap:= [10]string{
         "", // 0
        "", // 1
        "abc", // 2
        "def", // 3
        "ghi", // 4
        "jkl", // 5
        "mno", // 6
        "pqrs", // 7
        "tuv", // 8
        "wxyz", // 9
    }
    res:=make([]string,0)
    recursion("",digits,0,digitsMap,&res)
     return res
}
func recursion(tempString ,digits string, Index int,digitsMap [10]string, res *[]string) {//index表示第几个数字
    if len(tempString)==len(digits){//终止条件，字符串长度等于digits的长度
        *res=append(*res,tempString)
        return
    }
    tmpK:=digits[Index]-'0' // 将index指向的数字转为int（确定下一个数字）
    letter:=digitsMap[tmpK]// 取数字对应的字符集
    for i:=0;i<len(letter);i++{
        tempString=tempString+string(letter[i])//拼接结果
        recursion(tempString,digits,Index+1,digitsMap,res)
        tempString=tempString[:len(tempString)-1]//回溯
    }
}